In many environments data in various forms (e.g., various protocols, modulations, etc.) can be transmitted over a channel from a transmitter to a receiver. Depending on the type and circumstances of operation, some channels are more or less prone or susceptible to loss or degradation of the data being transmitted over the channel, with differing channels having differing degrees of potential loss or corruption. For example, a wireline channel typically has a relatively higher degree of integrity and reliability than a channel existing over a radio or interface.
Detection of loss or inaccurate transmission of data over a channel is possible when certain additional information in the form of an error detection code is added to the data stream. For example, at a receiver a frame or block of data can have appended to it an error detection code in the form of (for example) a check character(s) or check sum which is computed or otherwise derived from the block. Upon reception of the block by the receiver, the receiver can independently recompute or re-derive the error detection code (e.g., the receiver's version of the check character(s) or check sum). If the recomputed or re-derived error detection code (e.g., check sum) is the same as the error detection code included in the received block or frame, the receiver can confirm that the block or frame is correctly decoded.
In addition to error detection techniques, error correcting techniques are also known. For example, error correction codes (generated by polynominals that operate over a frame or block of user data) can also be added to the data stream. Upon reception of the complete frame or block, using the known error correction code/technique the receiver can locate and correct certain errors in the data stream.
A convolutional code is a forward error-correction scheme, whereby the coded sequence is algorithmically achieved through the use of current data bits plus some of the previous data bits from the incoming stream. In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n≧m) and (b) the transformation is a function of the last k information symbols, where k is the constraint length of the code. A trellis description of a convolutional encoder shows how each possible input to the encoder influences both the output and the state transitions of the encoder.
A convolutional code (CC) is called tail-biting (or circular) if the beginning state of its encoding trellis is always equal to the ending state of its encoding trellis after encoding. Tail-biting convolutional codes (TBCC) are simple and powerful forward error correction (FEC) codes, as described, e.g., in H. H. Ma and J. K. Wolf, “On tail biting convolutional codes,” IEEE Trans. Commun., vol. 34, pp. 104-111, February 1986.
Tail-biting convolutional codes (TBCC) are employed in many environments, including telecommunication networks having an air, radio, or “wireless” interface. Tail-biting convolutional codes (TBCC) have been adopted as the mandatory channel codes for the data channels and the overhead channels (like frame control header) in 802.16 WiMAX (Worldwide Interoperability for Microwave Access) system. 802.16 WiMAX is described, e.g., in IEEE Std 802.16-2004, “IEEE Standard for Local and Metropolitan Area Networks—Part 16: Air Interface for Fixed Broadband Wireless Access Systems”, October, 2004; and IEEE Std P802.16e-2005, “IEEE Standard for Local and Metropolitan Area Networks—Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems”, February, 2006, both of which are incorporated herein by reference. They have also been adopted as the channel codes for the header channel in the EDGE system and for the control channel in the IS-54 system. For a description of the EDGE system, see, e.g., M. Mzyece and J. Dunlop, “Performance evaluation of suboptimal decoding schemes for tail biting convolutional codes in EDGE headers,” IEE Electronics Letters, vol. 39, no. 17, pp. 1280-1281, August 2003, incorporated herein by reference. For a description of the IS-54 system, see, e.g., R. V. Cox and C.-E. W. Sundberg, “An efficient adaptive circular viterbi algorithm for decoding generalized tailbiting convolutional codes,” IEEE Trans. Veh. Technol., vol. 43, pp. 57-68, February 1994, incorporated herein by reference.
As indicated above, a convolutional code (CC) is called tail-biting (or circular) if the beginning state of its encoding trellis is always equal to the ending state of its encoding trellis after encoding. For a feedforward CC, the beginning state is simply determined by the last v input bits, where v is the overall constraint length. See, e.g., H. H. Ma and J. K. Wolf, “On tail biting convolutional codes,” IEEE Trans. Commun., vol. 34, pp. 104-111, February 1986. Johannesson and K. S. Zigangirov, Fundamentals of convolutional coding. Piscataway, N.J.: IEEE Press, 1999; S. Lin and D. J. Costello, Jr, Error control coding. Upper Saddle River, N.J.: Pearson, 2004; all incorporated herein by reference. For a feedback CC, the encoder structure has to comply with certain conditions so that the circular encoding is possible. See, e.g., C. Berrou, C. Douillard and M. Jezequel, “Multiple parallel concatenation of circular recursive convolutional (CRSC) codes,” Annals of Telecommunications, vol. 54, No 3-4, pp. 166-172, March-April 1999; and Y.-P. Wang, R. Ramesh, A. Hassan, and H. Koorapaty, “On MAP decoding for tail-biting convolutional codes,” IEEE International Symposium on Information Theory (ISIT) 1997, pp. 225, June 1997; both incorporated herein by reference.
In both cases (feedforward and feedback CC) the beginning state (also called the circular state) of the encoding trellis is determined from the input information bit vector. That is, the beginning state is not always equal to the all-zero state and depends on the values of the input bits. However, the information on the circular state is not available to the receiver. Therefore one important task in the decoder for decoding TBCC is to estimate the circular state based on the received soft bit metrics.
There are many advantages of using a Tail-biting convolutional code (TBCC) over the conventional zero-tail convolutional codes (ZTCC) and some block codes. Among the advantages are the following:
1. A zero-tail convolutional code (ZTCC) needs to use v redundant zero-tail bits to terminate the encoding trellis to the all-zero state. In a Tail-biting convolutional code (TBCC), zero-tail bits are not needed and they can be replaced by payload bits to increase the spectral efficiency of the channel code.
2. Many good block codes can be generated by equivalent TBCC's (see, e.g., P. Ståhl, J. B. Anderson and R. Johannesson, “Optimal and near-optimal encoders for short and moderate-length tail-biting trellises,” IEEE Trans. Inform. Theory, vol. 45, pp. 2562-2571, November 1999, incorporated herein by reference), and hence can be decoded by the more efficient soft-input soft-output decoding algorithms for trellis codes. See, e.g., R. Y. Shao, S. Lin and M. P. C. Fossorier, “Two decoding algorithms for tail-biting codes,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1658-1665, October 2003; R. Johannesson and K. S. Zigangirov, Fundamentals of convolutional coding. Piscataway, N.J.: IEEE Press, 1999; S. Lin and D. J. Costello, Jr, Error control coding. Upper Saddle River, N.J.: Pearson, 2004, all incorporated herein by reference.
In order to achieve the superior performance of Tail-biting convolutional codes (TBCC), the circular state (or the probability distribution of the beginning states in terms of state metrics) needs to be efficiently and accurately estimated before or jointly with the decoding process. Many efficient algorithms have been proposed for estimating the circular state (or the probability distribution of the beginning states in terms of state metrics) of and decoding a Tail-biting convolutional code (TBCC). These algorithms can roughly be divided into two categories. A first category is the maximum likelihood (ML) Viterbi-type algorithms (See, e.g., R. Y. Shao, S. Lin and M. P. C. Fossorier, “Two decoding algorithms for tail-biting codes,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1658-1665, October 2003, incorporated herein by reference). A second category is the maximum a posteriori probability (MAP) BCJR-type algorithms. See, e.g., L. R. Bahl, J. Cocke, F. Jelink, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inform. Theory, vol. 20, pp. 284-287, March 1974; and J. B. Anderson and S. M. Hladik, “Tailbiting MAP decoders,” IEEE J. Select. Areas Commun., vol. 16, pp. 297-302, February 1998, incorporated herein by reference.
The technology described herein focuses primarily on the low-complexity Viterbi-type algorithms. Among them, the wrap-around Viterbi algorithm (WAVA) provides good compromises between performance and complexity. The low-complexity Viterbi-type algorithms are described, e.g., by R. Y. Shao, S. Lin and M. P. C. Fossorier, “Two decoding algorithms for tail-biting codes,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1658-1665, October 2003, incorporated herein by reference. WAVA is briefly summarized below.
The wrap-around Viterbi algorithm (WAVA) is based on the property that the starting and ending states in the trellis of a tail-biting code are the same and therefore the trellis can be viewed as a cylinder by connecting the beginning and ending parts of the trellis together. Then the conventional Viterbi algorithm is conducted over the decoding trellis for several cycles (or iterations) to improve the estimation of the probability distribution of the beginning states (in terms of state metrics). Let M=2v be the number of states in the trellis, L the length of the trellis (or the number of trellis stages), and let I be the maximum number of cycles (or iterations) allowed in the wrap-around Viterbi algorithm (WAVA). Let (ρbest(i),mbest(i)) be the best path and its path metric up to iteration i, and let (ρTB,best(i),mTB,best(i)) be the best tail-biting path (TBP) and its path metric up to iteration i. As used herein, a best path (whether tail-biting or not) “up to iteration i” means the best path thus far encountered in all iterations including the current iteration i. On the other hand, let (σbest(i),τbest(i)) be the best path and its path metric during iteration i, and let (ρTB,best(i),mTB,best(i)) be the best tail-biting (TBP) and its path metric during iteration i. A tail-biting path (TBP) here is defined as a decoded path with the same beginning state and ending state. Therefore, it is possible that the decoder can not find σTB,best(1)during iteration i. Note that the state metrics are accumulated from the very first iteration, and are used in the selection of survivor paths in the Viterbi algorithm. However, the selection of the best path and the best tail-biting path (TBP) during each iteration are based on the path metrics, which are equal to ending states' metrics subtracted by the beginning states' metrics during one iteration. During iteration i, if τbest(i)is larger than mbest(i-l), (ρbest(i),mbest(i)) will be updated to (σbest(i),τbest(i)); otherwise, (ρbest(i),mbest(i)) will be set to the previous values (ρbest(i-l),mbest(i-l)). The same rules apply to the update for the best TBP.
The conventional wrap-around Viterbi algorithm (WAVA) can be described by the following sequence of acts or steps:
(act 1) Initialize all the M number of beginning states' metrics to zero so that all beginning states are equally likely.
(act 2) For the first iteration, the conventional Viterbi algorithm is conducted to find the M number of survivor paths at the M number of ending states. If the best path (with the largest path metric) among the M number of survivor paths is a tail-biting path (TBP), then the decoding process is terminated and the decoder outputs the best path as the decoded sequence; otherwise, record (ρbest(1),mbest(1)) and (ρTB,best(1),mTB,best(1)) if the pair exists.
(act 3) At iteration i, i>1, the state metrics for the M number of beginning states are initialized by the state metrics of the M number of final states from iteration (i-1), and the conventional Viterbi algorithm is conducted to find the M number of survivor paths at the M number of ending states. At the end of iteration i, both (ρbest(i),mbest(i)) and (ρTB,best(i),mTB,best(i)) are updated. If ρTB,best(i) exists and satisfies some termination condition, the decoding process is terminated and the decoder outputs ρTB,best(i) as the decoded sequence. Otherwise act 4 is performed.
(act 4) Repeat act 3 until either the decoding process is terminated (due to the satisfaction of some termination condition) or the maximum number of iterations I is reached.
(act 5) The decoder outputs ρbest(I) as the decoded sequence if it exists. Otherwise, the decoder outputs ρbest(I) as the decoded sequence.
In act 3 above, two possible termination conditions (or stopping rules) can be used (See, e.g., R. Y. Shao, S. Lin and M. P. C. Fossorier, “Two decoding algorithms for tail-biting codes,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1658-1665, October 2003, incorporated herein by reference). The first possible termination condition is called the simple termination condition where ρTB,best(i)=ρbest(i); that is, the best path up to iteration i is the best tail-biting path (TBP) up to iteration i. The second possible termination condition is called the sufficient termination condition, where the metric of the best tail-biting path (TBP) up to iteration i (mTB,best(i)) is compared with some adaptive threshold. The sufficient condition will guarantee that the output tail-biting path (TBP) is the maximum likelihood (ML) solution. The details of the sufficient termination condition can be found in R. Y. Shao, S. Lin and M. P. C. Fossorier, “Two decoding algorithms for tail-biting codes,” IEEE Trans. Commun., vol. 51, no. 10, pp. 1658-1665, October 2003, incorporated herein by reference).
In general, the performances with the above two termination conditions are almost identical and are very close to the optimum maximum likelihood (ML) decoding performance. See, e.g., T.-T. Jason Chen, S. Shawn Tsai, “Final report on 2005 WiMAX link simulation,” 05/0363-6/FCP101 3630 Uen, Ericsson Internal Technical Document, March 2006, incorporated herein by reference. However, the decoder with the sufficient termination condition requires less average number of iterations (cycles) with the cost of higher complexity (from the computation and storage of thresholds) than the decoder with the simple termination condition.
There are, however, problems with existing solutions. For example, during the iterations in wrap-around Viterbi algorithm (WAVA), both (ρbest(i),mbest(i)) and (ρTB,best(i),mTB,best(i)) need to be stored and updated after each iteration. The storing and updating of the (ρbest(i),mbest(i)) and (ρTB,best(i),mTB,best(i)) values requires more computational complexity and memory usage, especially when the packet length is long or when the average number of iterations (cycles) needed by wrap-around Viterbi algorithm (WAVA) is large (like over the low SNR region). The higher computational complexity and larger memory usage are not desirable, especially in a radio access network application and particularly in a wireless terminal (e.g., on the mobile station terminal side).